//归并排序

#pragma once

//归并两个有序序列 a[low..mid] 和 a[mid+1..high]
//为一个有序序列
template <typename E>
void Merge(E a[], E b[],int low, int mid, int high)
{
    //归并序列 a[low..mid] 和 a[mid+1..high] 到 b[low..high]
    int i = low, j = mid + 1, k = low;
    while(i<=mid && j<=high)
        b[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
    while(i<=mid) b[k++] = a[i++];
    while(j<=high) b[k++] = a[j++];  

    //复制 b[low..high] 到 a[low..high]
    for(int i=low; i<=high; i++) a[i] = b[i];
}

//归并排序
template <typename E>
void MSort(E a[], E b[], int low, int high)
{
    if(low >= high) return;

    int mid = (low+high)/2;
    MSort(a, b, low, mid);
    MSort(a, b, mid+1, high);
    Merge(a, b, low, mid, high);
}

//归并排序
template <typename E>
void MergeSort(E a[], int n)
{
    auto b = new E[n];
    MSort(a, b, 0, n-1);
    delete[] b;
}